package org.laizili.solution.leetcode;

import java.util.*;

import org.laizili.structure.tree.multitree.Node;
/**
 * <a href="https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/">429. N 叉树的层序遍历</a>
 * <p>
 * tags: BFS; 树的层序遍历（模板）
 * </p>
 * <p>
 * notes: 应用树的不同遍历方式解决关于树的问题
 * </p>
 */
public class Problem429 {
    private static class Solution {
        public List<List<Integer>> levelOrder(Node root) {
            if (root == null) {
                return Collections.emptyList();
            }
            Queue<Node> nodes = new ArrayDeque<>();
            nodes.add(root);
            List<List<Integer>> res = new ArrayList<>();
            while (!nodes.isEmpty()) {
                int cnt = nodes.size();
                List<Integer> hire = new ArrayList<>(cnt);
                res.add(hire);
                for (int i = 0; i < cnt; i++) {
                    Node node = nodes.poll();
                    hire.add(node.val);
                    if (node.children != null) {
                        for (Node child : node.children) {
                            if (child != null) {
                                nodes.offer(child);
                            }
                        }
                    }
                }
            }
            return res;
        }
    }
}
